![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
Counting Fixed Points Over All Keys. The distribution of the number of permutation fixed points for various key sizes is given in Table 7.3. A fixed point of an S-box si is a value x for which x = si(x). This metric does not necessarily have any direct cryptographic significance. However, it is a useful way to verify that the S-boxes are behaving similarly to random S-boxes, since it is possible to compute the theoretical distribution of fixed points for random S-boxes. The probabilities for random bijective S-boxes is given in the last row. (The probability of n fixed points is approximately e1/n!.) The Twofish S-box distributions of fixed points over all keys match theory fairly well.
Differences between S-boxes. The metrics discussed so far give us a fair level of confidence that the Twofish method of constructing key-dependent S-boxes does a reasonable job of approximating a random set of S-boxes, when viewed individually. Another possible concern is how different the various Twofish S-boxes are from each other, for a given key length. This issue is of particular interest in dealing with related-key attacks, but it also has an important bearing on the ability of an attacker to model the S-boxes. Despite the fact that the Twofish S-boxes are key dependent, if the entire set (or large subsets) of S-boxes, taken as a black box, are very closely related, the benefit of key dependency is severely weakened. As a pathological example, consider a fixed 8-bit permutation q[x] which has very good DPmax and LPmax values, but which is used as a key-dependent family of S-boxes simply by defining sk(x) = q[x]⊕k. It is true that each sk permutation also has good individual metrics, but the class of s permutations is so closely related that conventional differential and linear cryptanalysis techniques can probably be effectively applied without knowing the key k. The Twofish S-box structure has been carefully designed with this issue in mind.
For example, if an attacker wants to perform a differential attack that is not key dependent, then he can view each S-box as a series of q-boxes and XORs with key bytes. The direct consequence is that he needs to use 3 to 5 differential characteristics of q-boxes per S-box, which makes the probability of any differential characteristic much smaller.
In one class of related-key attacks, an attacker attempts to modify the key bytes in such a way as to minimize the differences in the round subkey values Ai, Bi. Since the Twofish S-box structure is used in computing Ai and Bi, with Me and Mo. as key material, respectively, a measure of the differential characteristics of Ai (or Bi) across keys M will help us understand both how different the S-boxes are from each other and how likely such an attack is to succeed.
To this end, let us first look at how many consecutive values of Ai with a fixed XOR difference can be generated for two different keys. That is, if Ai is the sequence for the key M and A´i is the sequence for the key M´, then we want to examine how many consecutive Ai, A´i satisfy Ai ⊕ A´i = δ for some fixed XOR difference δ. A nearly identical argument holds for the Bi, so we can restrict our attention to the Ai, and furthermore, we can consider only those changes which affect Me, the key material used by the S-boxes when computing Ai.
If we let yi be the output sequence for one S-box used in generating the Ai, and y´i the output sequence for the same S-box when generating the A´i, then we can consider the difference sequence y* = yi ⊕ y´i. For example, in the 128-bit key case, with 16 bits of key material per S-box, there are about 231 distinct pairs of keys for each S-box, so there would be 231 such difference sequences, each of length 20. We can then consider the probability of having a run of n consecutive equal values in the sequence. If n can be made to approach 20, then a related-key attack might be able to control the entire sequence of Ai values, and, even worse, our belief in the independence of the key-dependent S-boxes must be called seriously into question. Note that an attacker has exactly 16 bits of freedom for a single S-box in the 128-bit key case, so intuitively it seems unlikely that he should be able to force a given difference sequence that is very long.
Table 7.4 shows the distribution of run lengths of the same XOR difference y*i for consecutive i. For random byte sequences, we would theoretically expect that Pr(XOR run length = n) should be roughly 28(n1), which matches quite nicely with the behavior observed in the table. It can be seen that the probability of injecting a constant difference into more than five consecutive subkey entries is extremely low, which is reassuring.
log2(Pr(XOR run length = n)) | |||||||
Key Size | Max Value | n = | 1 | 2 | 3 | 4 | 5 |
128 bits | 5 | 0.01 | 7.98 | 15.95 | 23.89 | 30.00 | |
192 bits* | 4 | 0.01 | 7.98 | 15.93 | 23.69 | ||
256 bits* | 5 | 0.01 | 7.98 | 15.93 | 24.02 | 30.29 |
log2(Pr(max # equal XOR differences = n)) | ||||||||
Key Size | Max Value | x = | 1 | 2 | 3 | 4 | 4 | 6
|